Communication systems or networks, such as those used to deliver telecommunications, to deliver video images, to interconnect computers, to provide conventional cellular communications, and the like, may include any number of nodes. These networks may deliver electronic communications between two points by routing the communications content from node to node within the network. As the number of nodes in a network increases and as the number of communication paths available to each network node increases, the number of potential paths available for delivering any single communication likewise increases. As the number of potential paths which are available increases, a problem of selecting an appropriate path through the network arises. Typically, it is advantageous for the network to attempt to select the shortest possible path to minimize delay, to consume a minimal amount of network resources, and to maximize reliability in delivering communications, information flow, or other service. At the same time, actions within the network need to balance the constraints of the delay, resource consumption, and reliability with the need to prevent overloading any of the network nodes or communication links, while maintaining delivery of the network traffic. Delivery of network traffic to its intended destination is desirably made with proper allowances for statistical variations in traffic and an ability for the network to absorb instantaneous changes in requested service without having to react to the volume of traffic by devising new routing instructions.
In a global communication system where nodes are space based, simplicity and robustness are key ingredients in implementing a practical and operationally useful routing scheme. In addition, the nodes of such a system may move with respect to one another, thereby introducing variations in both link capacity and demand which should be accounted for naturally and simply in the methodology. Furthermore, minimal exchange in the network is desirable in order to minimize node copy complexity and simplify route management. Minimal exchange of any route information also results in increased reliability and reduced cost.
Routing in dynamic or moving systems or networks, has generally required near real time exchange of routing update information among the network nodes. Significant nodal decision making processing has also been common within the nodes. While both real time update and significant nodal decision making are possible, a simpler technique is desirable from simplicity, cost, and increased reliability standpoints. In addition inter-satellite propagation delays which are longer than their terrestrial counterpart exacerbate the difficulties of properly synchronizing the nodal decision making to update routing decisions with the most current information and to then develop the best routing instructions or decisions.
There are a number of alternative methodologies that may be applied to the task of determining routing within a moving and dynamic communication system. The first is centralized where updated routes are calculated in a centralized location and the information is either transmitted to each node in the form of a table, or otherwise distributed to each call processing entity and used therein to select the optimum route at the time of a connections is to be established between the source and destination nodes. A form of this methodology is called source routing and has been implemented by some existing packet networks such as Tymnet. However, in ground based communication networks such as in Tymnet, all calls are normally processed by a single central supervisor which calculates and maintains the updated route information for each possible source-destination pair in the network. Since that single resource selects routes for each communication and assigns so-called "virtual circuit" identifiers to each, the uniqueness of such route identification is maintained for all communication needs throughout the network, and no confusion is created when several communications cross simultaneously through one intermediate node on their journey through the network.
The situation is quite different in a global satellite based communication network where both the space-borne nodes and the terrestrial interconnect points share the communication processing load and may share in the generation and attachment of connection identification as part of the inter nodal transmissions. If used, then careful attention is needed to keep track of the virtual circuit identifiers assigned to in real-time by the processing nodes so that the same virtual circuit is not re-used by another node in identifying a route for a new connection. The complexity and inefficiency associated with real-time exchange of route identification information among several remotely located nodes in a global satellite based communication network is both undesirable and unnecessarily expensive.
Thus what is needed is a method and apparatus of routing information packets among nodes in a communication system where the nodes are moving with respect to each other, and where the connections or links between the nodes are also changing as a function of the position of the node. What is also needed is a highly distributed routing method that is implemented autonomously by each node. What is also needed is a routing method which achieves uniformity in the usage of network links while limiting the number of hops between source and destination on each path used for routing. What is also needed is a routing method which uses the available resources, prevents link congestion and at the same time allows for the statistical variations which occur due to the random arrival and departure of users of the system.